#include <iostream>
#include <cstdlib>
#include <vector>


/*
   Output a vector with a newline.
*/
template <typename T>
void print_vector(const std::vector<T>& to_print)
{
    std::cout << "[";
    // Using long as required to be able to compare as signed long.
    for (long x = 0; x < (long(to_print.size())-1); x += 1) {
        std::cout << to_print.at(x) << ", ";
    }
    if (to_print.size() > 0)
        std::cout << to_print.back();
    std::cout << "]" << std::endl;
}


template <typename T>
std::vector<T> quicksort(const std::vector<T>& to_sort)
{
    if (to_sort.size() <= 1)
        return to_sort;
    else {
        /* Get pivot. */
        T pivot = to_sort.at(0);
        std::vector<T> le;
        std::vector<T> gt;

        /* Sort on pivot. */
        for (unsigned long x = 1; x < to_sort.size(); x += 1) {
            T item = to_sort.at(x);

            if (item <= pivot)
                le.push_back(item);
            else
                gt.push_back(item);
        }

        /* Sort sub-vectors. */
        std::vector<T> sorted_le = quicksort(le);
        std::vector<T> sorted_gt = quicksort(gt);

        /* Combine sort results into a single vector. */
        std::vector<T> total_sort;
        total_sort.resize(1 + sorted_le.size() + sorted_gt.size());

        total_sort.assign(sorted_le.begin(), sorted_le.end());
        total_sort.push_back(pivot);
        copy(sorted_gt.begin(), sorted_gt.end(), total_sort.end());

        return total_sort;
    }
}


// Ditched 'const' modifier in order to use iterators.
template <typename T>
std::vector<T> heapsort(std::vector<T>& part1,
                        std::vector<T>& part2)
{
    std::vector<T> sorted;

    // Don't know why typename is required.
    typename std::vector<T>::iterator part1_iter = part1.begin();
    typename std::vector<T>::iterator part1_end = part1.end();
    typename std::vector<T>::iterator part2_iter = part2.begin();
    typename std::vector<T>::iterator part2_end = part2.end();

    // Tried to make generic by assigning iterators first and then performing
    // operation, but iterator advancement was not working until I assigned the
    // result of ++.
    while ((part1_iter != part1_end) && (part2_iter != part2_end)) {
        if (*part1_iter <= *part2_iter) {
            sorted.push_back(*part1_iter);
            part1_iter = ++part1_iter;
        }
        else {
            sorted.push_back(*part2_iter);
            part2_iter = ++part2_iter;
        }
    }

    // Tried to do this generically using for_each() and vector::push_back(),
    // but couldn't find a way to do a bound method without defining my own
    // object.
    std::vector<T> exhaust;
    T start_from;
    T end_at;
    if (part1_iter == part1_end) {
        exhaust = part2;
        // Funky math below required as didn't know of a way to find out the
        // position of an iterator.
        end_at = part2.size();
        start_from = end_at - (part2_end - part2_iter);
    }
    else {
        exhaust = part1;
        end_at = part1.size();
        start_from = end_at - (part1_end - part1_iter);
    }
    for (unsigned long x = start_from; x < end_at; x += 1)
        sorted.push_back(exhaust.at(x));

    return sorted;
}


int
main(int argc, char *argv[])
{
    /* Create a vector of "random" numbers. */
    unsigned long count = std::atol(argv[1]);
    std::vector<unsigned long> random;
    for (unsigned long x = count; x != 0; x -= 1)
        random.push_back(x);

    /* Split vector in half. */
    std::vector<unsigned long>::iterator middle = random.begin() +
                                                    (random.size() / 2);
    unsigned long half_len = random.size() / 2;
    std::vector<unsigned long> front_half;
    front_half.resize(half_len);
    std::vector<unsigned long> back_half;
    back_half.resize(random.size() - half_len);

    copy(random.begin(), middle, front_half.begin());
    copy(middle, random.end(), back_half.begin());

    /* Quicksort each half. */
    std::vector<unsigned long> sorted_front =
                                        quicksort<unsigned long>(front_half);
    std::vector<unsigned long> sorted_back =
                                        quicksort<unsigned long>(back_half);

    /* Heapsort into a single vector. */
    std::vector<unsigned long> complete_sort;
    complete_sort = heapsort<unsigned long>(sorted_front, sorted_back);
    print_vector<unsigned long>(complete_sort);
}
